package nowercoder.basics.exce01;

import java.util.Arrays;

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;

        int key = arr[left];
        int l = left;
        int r = right;

        while (l < r) {
            while (l < r && arr[r] > key) r--;
            while (l < r && arr[l] <= key) l++;
            swap(arr, l, r);
        }

        arr[left] = arr[l];
        arr[l] = key;

        quickSort(arr, left, l - 1);
        quickSort(arr, l + 1, right);
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] ar = {1, 3, 2, 5, 3, 6, 2, 78, 34, 99, 23};
        quickSort(ar, 0, ar.length - 1);
        System.out.println(Arrays.toString(ar));
    }
}
